#include <bits/stdc++.h>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode, *LinkedList;

bool Init(LinkedList &L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    if (L == NULL)
        return false;
    return true;
}

bool Insert(LinkedList &L, int a) {
    LNode *p = L;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->data = a;
    while (p->next != NULL)
        p = p->next;
    p->next = s;
    s->next = NULL;
    return true;
}

void PrintList(LinkedList L) {
    LNode *p = L;
    while (p->next != NULL) {
        p = p->next;
        if (p->next == NULL)
            cout << p->data;
        else
            cout << p->data << "->";
    }
    cout << endl;
}

void ChangeList(LinkedList &L) {
    LNode *slow = L;
    LNode *fast = L;
    while (fast->next != NULL) { // 寻找中间结点
        slow = slow->next;
        fast = fast->next;
        if (fast->next != NULL)
            fast = fast->next;
    }
    LNode *p = slow->next;  //  slow所指结点为中间结点，p为链表后半段的首结点
    slow->next = NULL;
    slow = slow->next;
    while (p != NULL) { //  将链表的后半段逆置
        LNode *r = p->next;
        p->next = slow;
        slow = p;
        p = r;
    }
    // 此时slow指向链表的后半段逆置后的首结点
    // 令P指向链表前半段的首结点
    p = L->next;
    // 将链表的后半段插入指定位置
    while (slow != NULL) {
        LNode *r = slow->next;
        slow->next = p->next;
        p->next = slow;
        p = slow->next;
        slow = r;
    }
}

int main() {
    LinkedList L;
    Init(L);
    int num[] = {1, 2, 3, 4, 5, 6, 7, 8};
    for (int i = 0; i < 8; i++)
        Insert(L, num[i]);
    cout << "Input:" << endl;
    // 1->2->3->4->5->6->7->8
    PrintList(L);
    ChangeList(L);
    cout << "Result:" << endl;
    // 1->8->2->7->3->6->4->5
    PrintList(L);
    return 0;
}